//Given an array of characters chars, compress it using the following algorithm:
// 
//
// Begin with an empty string s. For each group of consecutive repeating 
//characters in chars: 
//
// 
// If the group's length is 1, append the character to s. 
// Otherwise, append the character followed by the group's length. 
// 
//
// The compressed string s should not be returned separately, but instead, be 
//stored in the input character array chars. Note that group lengths that are 10 or 
//longer will be split into multiple characters in chars. 
//
// After you are done modifying the input array, return the new length of the 
//array. 
//
// You must write an algorithm that uses only constant extra space. 
//
// 
// Example 1: 
//
// 
//Input: chars = ["a","a","b","b","c","c","c"]
//Output: Return 6, and the first 6 characters of the input array should be: [
//"a","2","b","2","c","3"]
//Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3
//".
// 
//
// Example 2: 
//
// 
//Input: chars = ["a"]
//Output: Return 1, and the first character of the input array should be: ["a"]
//Explanation: The only group is "a", which remains uncompressed since it's a 
//single character.
// 
//
// Example 3: 
//
// 
//Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
//Output: Return 4, and the first 4 characters of the input array should be: [
//"a","b","1","2"].
//Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
// 
//
// 
// Constraints: 
//
// 
// 1 <= chars.length <= 2000 
// chars[i] is a lowercase English letter, uppercase English letter, digit, or 
//symbol. 
// 
//
// Related Topics 双指针 字符串 👍 347 👎 0

package leetcode.editor.cn;

import static leetcode.editor.cn.P443StringCompression.Solution.compress;

class P443StringCompression{
    //2023-05-13 10:48:56
    //String Compression
    //编号：[443]

    public static void main(String[] args) {
        char[] chars = new char[]{'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'};
        System.out.println(compress(chars));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
static class Solution {

        public static int compress(char[] chars) {
            int index = 0;
            int length = chars.length;
            int count = 0;
            int newIndex = 0;
            while (index < length) {
                int next = index + 1;
                while (next < length && chars[index] == chars[next]) {
                    next++;
                }
                int num = next - index;
                int position = 0;
                chars[newIndex++] = chars[index];
                StringBuilder stringBuilder = new StringBuilder();
                if (num > 1) {
                    while (num > 0) {
                        stringBuilder.append(num % 10);
                        num = num / 10;
                        position++;
                    }
                }
                int len = stringBuilder.length();
                for (int i = len - 1; i >= 0; i--) {
                    chars[newIndex++] = stringBuilder.charAt(i);
                }
                count += position + 1;
                index = next;
            }
            return count;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}